|
In mathematical logic and logic programming, a Horn clause is a logical formula of a particular rule-like form which gives it useful properties for use in logic programming, formal specification, and model theory. Horn clauses are named for the logician Alfred Horn, who first pointed out their significance in 1951. == Definition == A Horn clause is a clause (a disjunction of literals) with at most one positive, i.e. unnegated, literal. Conversely, a disjunction of literals with at most one negated literal is called a dual-Horn clause. A Horn clause with exactly one positive literal is a definite clause; a definite clause with no negative literals is sometimes called a fact; and a Horn clause without a positive literal is sometimes called a goal clause (note that the empty clause consisting of no literals is a goal clause). These three kinds of Horn clauses are illustrated in the following propositional example: In the non-propositional case, all variables in a clause are implicitly universally quantified with scope the entire clause. Thus, for example: :¬ ''human''(''X'') ∨ ''mortal''(''X'') stands for: :∀X( ¬ ''human''(''X'') ∨ ''mortal''(''X'') ) which is logically equivalent to: :∀X ( ''human''(''X'') → ''mortal''(''X'') ) Horn clauses play a basic role in constructive logic and computational logic. They are important in automated theorem proving by first-order resolution, because the resolvent of two Horn clauses is itself a Horn clause, and the resolvent of a goal clause and a definite clause is a goal clause. These properties of Horn clauses can lead to greater efficiencies in proving a theorem (represented as the negation of a goal clause). Propositional Horn clauses are also of interest in computational complexity. The problem of finding truth value assignments to make a conjunction of propositional Horn clauses true is a P-complete problem, solvable in linear time, and sometimes called HORNSAT. (The unrestricted Boolean satisfiability problem is an NP-complete problem however.) Satisfiability of first-order Horn clauses is undecidable. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Horn clause」の詳細全文を読む スポンサード リンク
|